Dělitelnost čísel

Základní pojmy

Eukl(e)ides z Alexandrie , 365-300 př.n.l, řecký matematik, fyzik a hudební teoretik. Pokusil se odvodit všechny geometrické věty deduktivním postupem z několika základních axiomů a definic. Dokázal, že počet prvočísel je nekonečný. Jeho kniha 'Základy', se stala (spolu s biblí) nejčtenější knihou všech dob.

Celočíselné dělení

 Celočíselný podíl dvou čísel a,bεZ značíme a div b, zbytek po celočíselném dělení a mod b.

Platí: m∙(k div m) +(k mod m) = k,

Např. 14 div 3=4,  14 mod 3=2 a

3∙(14 div 3)+14 mod 3=3∙4 +2=14.

Když d je dělitelem čísla a (beze zbytku) píšeme d|a. 

Všechny možné zbytky podle modulu m utváří zbytkové třídy.

 Číselné obory – konečné, jednosložkové:
 Zr - zbytkové třídy podle modulu r (tj. Z podle modulu r)

Existují-li k číslům a,bεN taková čísla m,nεZ, že:  ma+nb=1, pak čísla a,b jsou nesoudělná.
Např.  žádné z čísel 30m±1 nemůže být dělitelné dvěma, třemi ani pěti (protože 30=2∙3∙5). Čísla tohoto tvaru menší než 72 jsou proto prvočísla (29,31) a čísla menší než 112 (59,61,89,91,119) jsou buď prvočísla nebo dělitelná sedmi.
Totéž platí i v případě, kdy a, b jsou celočíselné výrazy,
např. pro a=5s+2 b= 3s+1 je 3a−5b=1. Zlomek (5s+2)/(3s+1), tj.7/4,12/7,17/10,..., nemůže jít pro žádné s zkrátit [Horák].

Specielní přirozená čísla

Čísla tvaru 2k−1 se nazývají Mersennova čísla. Protože jsou všechna čísla nk−1 dělitelná (n−1), nabízí se zobecnit pojem Mersennových čísel na čísla M(n,k) = (nk−1)/(n−1).

Čísly tvaru nh+1 se zabýval (specielně v případě n=2 a h=2t) Pierre de Fermat, budeme je v obecnosti nazývat Fermatova čísla, F(n,h) = nh+1 (Obecněji se také pro  nh±1 používá pojmenování Cunninghamova čísla.)

  h     2h+1        3h+1      4h+1       5h+1         6h+1  

 ──────────────────────────────────────────────────────────

  1       3          4         5          6            7

  2       5         10        17         26           37

  3       9         28        65        126          217 

  4      17         82       257        626         1297

  5      33        244      1025       3126         7777

  6      65        730      4097      15626        46657

Pro lichá h jsou čísla K(n,h) = (nh+1)/(n+1) přirozená. Tato čísla se objevují při výpočtech s Kummerovými cyklickými čísly. Budeme je nazývat Kummerova čísla.

Parita čísel

Celá čísla se rozdělují podle parity na sudá a lichá.

Komplexní čísla a+bi je možné rozdělit do tří skupin (GaussII):

·         Lichá: tj.nedělitelná 1+i (jedno z čísel a, b liché a druhé sudé).

·         Polosudá: tj.dělitelná 1+i, ale nedělitelná 2 (každé z čísel a,b liché).

·         Sudá: tj. dělitelná 2 (každé z čísel a,b sudé).

Výraz (1+i)2 (i všechny sním vázané výrazy, např. (1−i)2, (1+i)(1−i),...) je dělitelný dvěmi. Proto aby číslo bylo sudé musí v jeho rozkladu existovat buď jeden sudý součinitel nebo dva polosudé součinitele. Polosudé ani sudé číslo nelze získat součinem lichých součinitelů.

Norma každého lichého komplexního čísla má tvar 4n+1, norma polosudého čísla tvar 2∙(4n+1) a norma sudého čísla tvar 2k∙(4n+1), k>2.

Např. N(1+2i)=5, N(3+3i)=18=2∙9, N(6+6i)=72=23∙9.

Sudá a lichá čísla celá čísla rozlišujeme na základě zbytků podle modulu 2. Lichá čísla (tj. čísla tvaru 2k+1) nyní dále zpodrobníme pro modul 4 a rozlišíme čísla tvaru 4s−1 (tj.4s+3) a čísla tvaru 4s+1.

Čísla tvaru 4s−1 (např. 3,7,11,15,19,23,27,31,35,39,43,47,...) nazveme ryzí lichá čísla, čísla tvaru 4s+1   (např. 1,5,9,13,17,21,25,29,33,37,41,45,49,...)  neryzí lichá čísla.

Největší společný dělitel

Dvě čísla a,bεN mají vždy nějakého největšího společného dělitele D=(a,b)≥1.

Vzájemně nesoudělná čísla, tj. čísla jejichž největší společný dělitel je 1, bývají nazývána vzájemně prostá čísla nebo též relativní prvočísla. To platí pro dvojice čísel, např.a,b, kde (a,b)=1. Pro n-tice čísel se vytvoří dvojice a říká se, že jde o čísla po dvou nesoudělná; např.a,b,c kde (a,b)=1, (a,c)=1 a (b,c)=1.

K hledání největšího společného dělitele (nsd) slouží tzv. Euklidův algoritmus. Ten vychází z postupných rozdílů čísel. Je-li totiž (pro a,b,dεN) d|a i d|b, platí i d|(a−b).

Číselně-teoretické funkce

Funkce f(n) jejichž argumentem (n) je celé číslo se nazývají číselně-teoretické funkce. Mezi nejznámější patří funkce τ() pro počet dělitelů čísla n, σ() pro součet dělitelů [Rychlík], Eulerova funkce φ() a Möbiova funkce μ().

Liouville Joseph [], 1809-1882, francouzský matematik, objevitel transcendentních čísel. Dokázal existenci transcendentních čísel a definoval konstrukci některých z nich (tzv. Liouvillova čísla). Do teorii čísel přispěl mimo jiné svými výzkumy kvadratických reprezentací a numerických funkcí. Zabýval se také diferenciální geometrií a matematickou analýzou.

 Liouvillova věta

Zajímavou aplikací funkce pro počet dělitelů čísla je tzv. Liouvillova věta.

Označme σ(r) počet dělitelů čísla r.
Např. číslo r=6 má celkem 4 dělitele {1,2,3,6}, tj. σ(6)=4. Přitom je σ(1)=1 a pro každé prvočíslo p je σ(p)=2,..Tak dostáváme postupně σ(1)=1, σ(2)=2, σ(3)=2 a σ(6)=4. Platí Liouvillova věta:

∑σ3 = (∑σ)2

V našem příkladě 13+23+23+43 = (1+2+2+4)2 = 81.

Obdobně např. pro r=30 s děliteli {1,2,3,5,6,10,15,30} dostaneme:

13+23+23+23+43+43+43+83 = (1+2+2+2+4+4+4+8)2 = 729.

Eulerova funkce

n\d 0 1 2 3 4 5 6 7 8 9 φ(n) ψ(n)
 ───────────────────────────────
 1: 0 - - - - - - - - - 1 0
 2: 0 1 - - - - - - - - 1 1
 3: 0 1 1 - - - - - - - 2 1
 4: 0 1 0 1 - - - - - - 2 2
 5: 0 1 1 1 1 - - - - - 4 1
 6: 0 1 0 0 0 1 - - - - 2 4
 7: 0 1 1 1 1 1 1 - - - 6 1
 8: 0 1 0 1 0 1 0 1 - - 4 4
 9: 0 1 1 0 1 1 0 1 1 - 3 6 
10: 0 1 1 0 0 0 1 0 1 0 4 6

Počet všech čísel dε(0,n−1), která jsou s daným číslem n nesoudělná, označíme φ(n). Číslo 0 se předpokládá být soudělné s každým číslem n, tj. (0,n)=n≠1, na rozdíl od čísla 1, pro které vždy (1,n)=1.

V tabulce jsou čísla (d,n)=1 označena jedničkou, ostatní nulou. Binární čísla v jednotlivých řádcích tabulky nazveme vzorky, počet jedniček v každém z nich úrovní vzorku. Počet jedniček v n-tém řádku, tj. úroveň vzorku délky n je hodnotou Eulerovy funkce φ(n).

Počet čísel soudělných s n označíme:

ψ(n) = n− φ(n)

V tabulce můžeme pozorovat některé vlastnosti Eulerovy funkce:

·         Když p je prvočíslo (pεP), je φ(p)=p−1, tj.ψ(p)=1

·         Pro hodnoty n=2k je φ(n)=ψ(n)=2k−1

·         Když d|k tak φ(d)|φ(k)

Pro mocniny nk platí:

φ(nk) = φ(n) nk−1

 Když vzorky dvou nesoudělných čísel, např. p=2, tj. [01] a q=3,

tj. [011], zopakujeme na délku p∙q =6, obdržíme [010101] a [011011].

Konjunkcí (logickým součinem) těchto hodnot je:

                  [010101] AND [011011] = [010001].

Výsledný vzorek pro číslo 2∙3 =6 má úroveň 2 tj. φ(2)∙φ(3) =φ(6).

Pro nesoudělná p,q obecně platí:

φ(p∙q)= φ(p)∙ φ(q)

Dělitelnost ve strukturách

Některé struktury se dvěma operacemi se chovají v souladu s pravidly známými z oboru celých čísel. Obdobou prvočísel a složených čísel jsou zde tzv. ireducibilní a reducibilní prvek. Analogicky se definují i další pojmy (největší společný dělitel, rozklad v součin prostých prvků, ...) a algoritmy (Euklidův algoritmus).

Jednoznačný rozklad v součin prostých prvků existuje jen v tzv. Gaussových okruzích. A Euklidův algoritmus funguje jen v tzv. Euklidových okruzích (např. okruhy celých čísel a polynomů), které tvoří podmnožinu Gaussových okruhů.

Wallise, John , 1616-1703, anglický matematik. Zabýval se nekonečnými řadami. Odvodil první vzorec pro výpočet čísla π, který neobsahoval odmocniny: π=2.(2.2.4.4.6.6...)/(1.3.3.5.5.7...). Imaginární čísla znázorňoval na kolmicích k reálným úsečkám.

Násobky komplexních čísel

S myšlenkou znázorňovat imaginární čísla na kolmicích k číslům reálným přišli J.Wallise, spolu s Casparem Wesselem (1745-1818) a Jeanem Robertem Argandem (1768-1822).

Na počest Arganda bývá zobrazení nazýváno Argandův diagram. U nás je běžnější pojmenování Gaussova rovina komplexních čísel.

Mějme např. komplexní číslo 2+i a hledejme jeho násobky. Násobením čísly 1,2,3,... dostaneme posloupnost bodů 2+i, 4+2i, 6+3i, atd. Body leží na přímce a vytváří novou pomyslnou osu X, která je vzhledem k původní soustavě souřadnic (0xy) skloněna. Na záporné straně této najdeme podobně body −2−i, −4−2i, −6−3i,... Kolmo na osu X prochází v bodě 0 osa Y, jejíž body −1+2i, −2+4i, −6+3i,... jsou (i)-násobky a body 1−2i, 2−4i, 3−6i,... (−i)-násobky první posloupnosti:

X+   2+i,  4+2i, 6+3i, ...        1

X−  −2−i, −4−2i,−6−3i, ...       −1

Y+  −1+2i,−2+4i,−3+6i, ...        i

Y−   1−2i, 2−4i, 3−6i, ...       −i

Kolmice v bodech 2+i a −1+2i se protínají v bodě 1+3i. V naší nové soustavě (0XY) má tento bod ale souřadnice 1+i. Platí: (2+i)(1+i) = 1+3i. Obdobně můžeme postupovat dále.

Všechny násobky čísla (2+i) tvoří čtvercovou síť bodů, jejichž souřadnice jsou (2+i)(r+si), kde r,sεZ. Přitom r+si udává souřadnice bodu v soustavě (0XY) a (2+i)(r+si) souřadnice bodu v soustavě (0xy).

Zbytek po dělení kvadratických čísel

Uvažujme dvě čísla A+B√d a a+b√d. Normu čísla a+b√d označme p, tj. p = a2+b2 = (a+b√d)(a−b√d). Zajímá nás výsledek operace A+B√d mod a+b√d. Výsledek označíme x+y√d a rovnici upravíme násobením číslem (a−b√d):

                      A+B√d mod a+b√d = x+y√d 

    (a−b√d)(A+B√d) mod (a−b√d)(a+b√d) = (a−b√d)(x+y√d)

             (aA−bBd)+(aB−bA)√d mod p = (a−b√d)(x+y√d)

Označíme f=(aA−bBd) mod p a g=(aB−bA) mod p a rovnici vynásobíme (a+b√d):

             f+g√d = (a−b√d)(x+y√d)

    (a+b√d)(f+g√d) = (a+b√d)(a−b√d)(x+y√d)

    (a+b√d)(f+g√d) = p(x+y√d)

Odtud:

           (x+y√d) = (a+b√d)(f+g√d)/p

                 x = (af+bgd)/p     y = (ag+bf)/p

V případě d=−1, tj. A+Bi mod a+bi = x+yi, je výsledkem:

 (x+yi) = (a+bi)(f+gi)/p,   x = (af−bg)/p    y = (ag+bf)/p

Při výpočtu čísel f a g je možné uvažovat nejmenší zbytky, tj. zbytky z intervalu <0,p−1>, nebo tzv. absolutně nejmenší zbytky, tj. zbytky z intervalu (−p/2,p/2>.


Prvočísla

Přirozená prvočísla

Eratosthenés z Kyrény , 275-194 př.n.l., řecký matematik,astronom a geograf, správce alexandrijské knihovny. Stanovil metodu určení poloměru Země, měřil sklon ekliptiky. Vytvořil první mapu založenou na astronomických pozorováních. Vynalezl přístroj na určování střední úměrné úsečky (tzv.mezolábium).

Prvočíslemse nazývá takové číslo pεN, kterého jediným dělitelem d<p (d|p) je číslo jedna (d=1).
Čísla tvaru pk budeme nazývat mocniny prvočísel. Součinem několika mocnin prvočísel jsou složená čísla.

K vyčlenění prvočísel z množiny přirozených čísel se používá tzv. Eratosthenovo síto.

Z čísel 2-25 získáme prvočísla ve třech krocích, postupným vyškrtáním násobků čísel 2,3 a 5 (tj. prvočísel nepřevyšujících √25):

Daná čísla:

2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25

Výsledky                          Vyškrtaná čísla

I/  2,3,5,7,9,11,13,15,17,19,21,23,25  4,6,8,10,12,14,16,18,20,22,24

II/ 2,3,5,7,11,13,17,19,23,25          (6),9,(12),15,(18),21,(24)

III/2,3,5,7,11,13,17,19,23             (10),(15),(20),25 

Mersennova prvočísla

Pro k = 2,3,5,7,13,17,19,31, .. jsou čísla M(2,k)=2k−1 prvočísla.

Když 2k−1 je prvočíslo, je i číslo k prvočíslo.

Nechť k má nějakého dělitele p>1, např. k=p∙q. Pak nk−1 = npq−1 = (np)q − 1q = (np−1)∙Q.

Mersenne, Marin [mersen], 1588-1648, francouzský mnich - matematik, hudební teoretik a filozof. Jeden z nejvýznamějších komunikačních článků vědy 17. století. Organizoval vědecké diskuze, dopisoval si s cca osmi desítkami učenců včetně Galilea, Huyghense, Torricelliho a Fermata.

Pro čísla M(n,k)=nk−1/(n−1) platí proto obdobné pravidlo jako pro 2k−1:

když číslo k je složené je i M(n,k) složené.

  k           M(2,k)εP             

 ────────────────────────

  2                 3

  3                 7

  5                31

  7               127

 13              8191

 17            131071

 19            524287

 31        2147483647

  

    k           M(3,k)εP             

   ────────────────────────

    3                13

    7              1093

   13            797161

 

    k           M(5,k)εP             

   ────────────────────────

    3                31

    7             19531

   11          12207031

   13         305175781

Fermatova prvočísla

Čísla nh+1 mohou být prvočísly jedině tehdy, když n je sudé číslo a h má tvar h=2t. Čísla F(2,2t) jsou tedy potenciálními prvočísly:

t F(2,2t)
──────────────────────────────────────────
0 3
1 5
2 17
3 257
4 65537
5 4294967297
6 18446744073709551617
7 340282366920938463463374607431768211457
Ne všechna F(2,2t) ale prvočísly jsou. To dokázal první Euler (čímž vyvrátil Fermatovu domněnku), 
když rozložil číslo 4294967297 na součin 641*6700417.


Protože 3∙5=17−2, 3∙5∙17=257−2, ..., je číslo M(2,2t)=  −1 = F(t)−2 pro libovolné t dělitelné všemi čísly F(2,i), i<t.  Čísla F(2,2t) souvisí s problémem konstrukce pravidelného n-úhelníka kružítkem a pravítkem (viz dále Gaussovy polygony).

Komplexní prvočísla

Komplexní prvočíslo nemá jiného dělitele než (některou) jednotku nebo sama sebe. Mezi komplexní prvočísla patří:

·         Číslo 1+i a s ním asociovaná čísla −1+i,−1−i,1−i

·         Ryzí lichá reálná nebo imaginární (kladná i záporná) prvočísla, tj. vždy čtveřice asociovaných čísel (tvaru 4n−1), např.: 7,−7,7i,−7i.
Tato čísla (např.3,7,−11,19i,...) nelze rozložit, protože součet dvou čtverců nemůže mít tvar 4n−1.

·         Čísla a+bi jejichž norma tvoří neryzí liché prvočíslo p (p>1), např. (1−2i), (−2+3i),... Protože rozklad normy tvaru 4n+1εP (např.5,13,17,...) v součet dvou čtverců je jednoznačný, přísluší každé normě vždy právě osm (vázaných) komplexních prvočísel.

Ostatní komplexní čísla jsou složená. Číslo 2 a neryzí lichá prvočísla (tj. čísla tvaru 4n+1 s výjimkou čísla 1) jsou složenými komplexními čísly:

  2=(1+i)(1−i), 5=(1+2i)(1−2i), 13=(2+3i)(2−3i), 17=(1+4i)(1−4i), atd.

Algoritmus podobný Eratosthenovu sítu je možné použít i v oboru komplexních čísel. Postupně se vyškrtávají všechny násobky čísel a+bi (ty tvoří dvourozměrnou síť bodů). Přitom za další číslo a+bi se vybírá vždy číslo s nejmenší normou (a2+b2).

Postupně takto dostaneme prvočísla: 1+i, 2+i, 3+2i, 4+i, 5+2i, 6+i, 5+4i,..., tj. čísla s normou 2, 5, 13, 17, 29, 37, 41, atd.

Rozklad v součin prvočinitelů

Přirozená čísla

Postupným a opakovaným dělením daného čísla k všemi prvočísly menšími než √k dostaneme rozklad čísla k v součin prvočinitelů . Např. 360=23∙32∙5.
Pro velká čísla je ale takový postup výpočetně náročný, zvláště nejsou-li daná čísla dělitelná malými prvočísly. Používají se proto některé zkratky, např. se využívá vztah a2−b2 = (a+b)∙(a−b):

    91=100−9  = (10−3)(10+3) = 7∙13

    119=144−25= (12−5)(12+5) = 7∙17

Komplexní čísla

Také každé komplexní číslo je rozložitelné na prvočíselné součinitele. Součinitel s může být vyjádřen jako součin primárního čísla a mocniny čísla i (i0 = 1, i1=i, i2 = −1, i3 = −i). Složené komplexní číslo může být proto zapsáno ve tvaru:

      M = iμ p1t1p2t2 ...

kde pj jsou různá, vzájemně prostá primární komplexní čísla a μ=0,1,2,3.

Eulerova kvadratická čísla

Součin dvou čísel tvaru m2+d∙n2 může být zapsán jako číslo téhož tvaru:

  (p2+d∙q2)(r2+d∙s2) = (pr−dqs)2+d∙(ps−qr)2   

Tento vztah inspiroval Eulera; při důkazu VF věty (viz kapitola X) pro exponent k=3 zavedl (r.1753) čísla a+b√−3 a ukázal že je možné použít Fermatovu metodu sestupu. Předpokládal, že v případě, kdy A+3B2 je třetí mocninou existuje k číslu A+B√−3 vždy jednoznačně určené číslo a+b√−3 takové, že platí:

         (a+b√−3)3 = A+B√−3

V případě čísel A+B√−3 Eulerův předpoklad platí (což bylo později dokázáno), obecně ale nelze použít. V okruhu čísel a+b√d nemají všechna čísla jednoznačný rozklad.

Např. v okruhu čísel a+b√−3 může být číslo 4 rozloženo dvěma způsoby:

     4= 2∙2 = (1+√−3)∙(1−√−3)

Okruh čísel a+b√−3 bývá také nazýván Eisensteinův okruh.

Okruh cyklických čísel

Problém s nejednoznačností rozkladu se opakoval o století později znovu. Francouzský matematik Lamé, oznámil (r.1847), že se mu podařilo s pomocí cyklických čísel dokázat obecný případ VF věty. V té době ale již cyklickými čísly zabýval německý matematik Kummer. Podrobným rozborem dokázal, že v případě k=23 jednoznačnost rozkladu selhává. Tedy nejjednoznačný rozklad v součin prvočísel mají také cyklická čísla.

Kummer, Ernst Eduard [], 1810-1893, německý matematik, autor teorie ideálů. Zabýval se diferenciální geometrií, kongruencí, objevil plochu čtvrtého řádu. Studium zákona reciprocity s pomocí cyklických čísel jej přivedlo ke vztahům, které bylo možné aplikovat také na Velkou Fermatovu větu. K odstranění nejjednoznačnosti rozkladu v součin prvočinitelů zavedl do teorie algebraických číselných těles tzv.ideální komplexní čísla. Dokázal (r.1850), že velká Fermatova věta platí pro každý exponent, který je regulárním prvočíslem.

Kummerova ideální čísla

Myšlenka se kterou vystoupil Lamé nakonec slavila úspěch. Kummer doplnil k cyklickým číslům tzv. ideální čísla a s pomocí nich dokázal VF větu v případech, kdy exponentem je tzv.

regulární prvočíslo. Protože cyklická čísla selhávají až v případě k=23, snáze se Kummerova metoda demonstruje na kvadratických číslech. Např. číslo 21 má dva možné rozklady v okruhu čísel a+b√−5.

      21 = 3 ∙ 7 = (1+2√−5)∙(1+2√−5)

Ideálními čísly A,B,C,D jsou taková čísla, že platí A∙B=3, C∙D = 7, A∙C=(1+2√−5) a B∙D=(1+2√−5).

    │      A       B       C        D

  ──┼─────────────────────────────────

  A │      ?       3  1−2√−5  ?

  B │      3       ?       ?   1+2√−5

  C │ 1−2√−5 ?       ?        7       

  D │      ?  1+2√−5 7        ?



Schematick? algebra